package clang.ir;

import fixedpoint.DataflowException;
import clang.CCodeGenerator;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * TODO Optimize multiplications with power of two constants
 * TODO node28813429 = -((signed long)node28050066);
 */
public class Dataflow {

    private Node root;
    private Node outputBufferConnection;
    private fixedpoint.ir.Dataflow fixedpointDataflow;
    ArrayList<Node> reachableNodeList;

    public Node getRoot() {
        return root;
    }

    // Hide ctor
    private Dataflow() {
        reachableNodeList = null;
    }

    public fixedpoint.ir.Dataflow getFixedpointDataflow() {
        return fixedpointDataflow;
    }

    /**
     * The order of nodes is undefined
     */
    public void buildReachableNodeList() {
        reachableNodeList = new ArrayList<Node>();
        ArrayList<Node> q = new ArrayList<Node>();
        q.add(root);
        if (outputBufferConnection != null) {
            q.add(outputBufferConnection);
        }
        while (!q.isEmpty()) {
            Node node = q.remove(0); // Remove queue head
            if (!reachableNodeList.contains(node)) {
                reachableNodeList.add(node);
                if (node instanceof Operator) {
                    Operator operator = (Operator) node;
                    int length = operator.childArrayLength();
                    for (int i = 0; i < length; i++) {
                        q.add(operator.getChild(i));
                    }
                }
            }
        }
    }

    /**
     * This task is very interesting
     */
    public void orderListOfReachableNodes() {
        root.buildEvaluationIndex(null);
        if (outputBufferConnection != null) {
            outputBufferConnection.buildEvaluationIndex(null);
        }

        //printEvaluationIndexes();

        // Sort nodes by evaluation index
        boolean flag = true;
        while (flag) {
            flag = false;
            int i;
            final int n = reachableNodeList.size();
            for (i = 0; i < (n - 1); i++) {
                if (reachableNodeList.get(i).getEvaluationIndex() > reachableNodeList.get(i + 1).getEvaluationIndex()) {
                    flag = true;
                    break;
                }
            }

            if (flag) {
                // Swap dataflow i with dataflow i + 1
                Node t = reachableNodeList.get(i);
                reachableNodeList.set(i, reachableNodeList.get(i + 1));
                reachableNodeList.set(i + 1, t);
            }
        }
    }

    /**
     * For debugging purposes
     */
    private void printEvaluationIndexList() {
        System.out.println("C-lang evaluation index list:");
        for (Node node : reachableNodeList) {
            System.out.println(node.getEvaluationIndex());
        }
    }

    public static Dataflow fixedpointDataflowToCLangDataflow(fixedpoint.ir.Dataflow fixedpointDataflow) throws DataflowException {
        if (fixedpointDataflow.isValid()) {
            Dataflow clangDataflow = new Dataflow();
            clangDataflow.root = fixedpointDataflowToCLangDataflow(fixedpointDataflow.getRoot());
            clangDataflow.buildOutputBufferConnection(fixedpointDataflow);
            clangDataflow.fixedpointDataflow = fixedpointDataflow; // cache
            return clangDataflow;
        } else {
            // This means that no node can overflow?...
            throw new DataflowException("Invalid dataflow");
        }
    }

    private static Node fixedpointDataflowToCLangDataflow(fixedpoint.ir.Node node) throws DataflowException {
        if (node instanceof fixedpoint.ir.Operator) {
            fixedpoint.ir.Operator operator = (fixedpoint.ir.Operator) node;

            ArrayList<fixedpoint.ir.Node> childNodes = operator.getChildNodes();
            final int n = childNodes.size();
            Node clangChild[] = new Node[n];
            for (int i = 0; i < n; i++) {
                clangChild[i] = fixedpointDataflowToCLangDataflow(childNodes.get(i));
            }

            return operator.toCLangNode(clangChild);
        } else {
            return node.toCLangNode();
        }
    }

    private void buildOutputBufferConnection(fixedpoint.ir.Dataflow fixedpointDataflow) throws DataflowException {
        fixedpoint.ir.Operator dfOutputBufferConnection =
                fixedpointDataflow.getOutputBufferConnection();
        if (dfOutputBufferConnection != null) {
            Node clangCenter[] = new Node[1];
            clangCenter[0] = null;

            // Get "accurate root"
            Stack<Node> stack = new Stack<Node>();
            stack.push(root);
            while (!stack.isEmpty()) {
                Node node = stack.pop();
                if (node instanceof Operator) {
                    if (node.getDescription().compareToIgnoreCase("accurate root") == 0) {
                        clangCenter[0] = node;
                        break;
                    } else {
                        ArrayList<Node> childNodes = ((Operator) node).getChildNodes();
                        for (Node childNode : childNodes) {
                            stack.push(childNode);
                        }
                    }
                }
            }

            if (clangCenter != null) {
                outputBufferConnection = dfOutputBufferConnection.toCLangNode(clangCenter);
                outputBufferConnection.setStorageClass(Node.StorageClass.INTERNAL_DECLARED);
            }
        }
    }

    /**
     * Returns the corresponding fixed-point code.
     * @return fixed-point C code
     */
    public String buildCLangCode() throws DataflowException {
        buildReachableNodeList();
        orderListOfReachableNodes();

        root.setStorageClass(Node.StorageClass.INTERNAL_DECLARED);
        declareNodesReadMultipleTimes();
        undeclareMultiplyNodes();

        String identation = CCodeGenerator.indentation(1);

        StringBuilder decl = new StringBuilder();
        //decl.append(identation).append("/* DECL */").append(Node.NEWLINE);

        StringBuilder def = new StringBuilder();
        //def.append(identation).append("/* DEF */").append(CCodeGenerator.NEWLINE);

        // Build the list of internal declared nodes
        Stack<Node> stack = new Stack<Node>();
        ArrayList<Node> internalDeclaredNodes = new ArrayList<Node>();
        // Select
        for (Node node : reachableNodeList) {
            if (node.getStorageClass() == Node.StorageClass.INTERNAL_DECLARED) {
                stack.add(node);
            }
        }
        // Reverse
        while (!stack.isEmpty()) {
            internalDeclaredNodes.add(stack.pop());
        }

        for (Node node : internalDeclaredNodes) {
            decl.append(identation);
            decl.append(node.getDatatype().toString()).append(" ").
                    append(node.getCLangName()).append(";");
            String description = node.getDescription();
            if (!description.isEmpty()) {
                decl.append(" /* ").append(description).append(" */ ");
            }
            decl.append(CCodeGenerator.NEWLINE);

            def.append(identation).append(node.getCLangName()).
                    append(" = ").append(node.getRuntimeExpression()).
                    append(";").append(CCodeGenerator.NEWLINE);
        }
/*
        if (outputBufferConnection != null) {
            Buffer outputBuffer = fixedpointDataflow.getFloatingpointDataflow().getOutputBuffer();

//            // Output buffer shift
//            decl.append(identation).append("signed int i;").append(CCodeGenerator.NEWLINE);
//            
//            def.append(CCodeGenerator.NEWLINE).append(identation).append("for (i = ").
//                    append(Integer.toString(outputBuffer.getLength() - 1)).append("; i > 0; i--) { ").
//                    append(outputBuffer.getName()).append("[i] = ").
//                    append(outputBuffer.getName()).append("[i - 1]; }").
//                    append(CCodeGenerator.NEWLINE);

            // Output buffer element 0 assignment
            if (outputBuffer != null) {
                // outputBufferConnection must be INTERNAL_DECLARED
                def.append(CCodeGenerator.NEWLINE).append(identation).append(outputBuffer.getName()).
                        append("[0] = ").append(outputBufferConnection.getCLangName()).
                        append("; ").append(CCodeGenerator.NEWLINE);
            } else {
                def.append("/* Internal error: null output buffer /");
            }
        }*/

        StringBuilder strBuilder = new StringBuilder(1 << 10); // 1K

        strBuilder.append(decl);
        strBuilder.append(CCodeGenerator.NEWLINE);
        strBuilder.append(def);

        strBuilder.append(CCodeGenerator.NEWLINE).append(identation).append("return ").
                append(root.getRuntimeValue()).append(";");

        return strBuilder.toString();
    }

    public String getCLangInfo() {
        StringBuilder sb = new StringBuilder();

        sb.append("/* ").
                append(CCodeGenerator.NEWLINE).
                append("This function is generated automatically.").
                append(CCodeGenerator.NEWLINE).
                append("Change of any parts may lead to range violations").
                append(CCodeGenerator.NEWLINE).append("and erroneous results.").
                append(CCodeGenerator.NEWLINE).append(CCodeGenerator.NEWLINE);

        if (fixedpointDataflow != null) {
            sb.append("Cost function applied:  ").
                    append(fixedpointDataflow.getCostFunctionApplied().toString()).
                    append(CCodeGenerator.NEWLINE);

            try {
                sb.append("Dataflow complexity signature:  ").
                        append(fixedpointDataflow.getRoot().getDataflowComplexitySignature()).
                        append(CCodeGenerator.NEWLINE);
                sb.append("Dataflow complexity:  ").
                        append(fixedpointDataflow.getComplexity()).
                        append(CCodeGenerator.NEWLINE);
            } catch (DataflowException ex) {
                sb.append(ex.toString());
            }

            try {
                sb.append("Error interval:  ").append(fixedpointDataflow.getRoot().getDrift()).
                        append(CCodeGenerator.NEWLINE);
            } catch (DataflowException ex) {
                sb.append(ex.toString());
            }
            
            sb.append("Transformation time:  ").append(fixedpointDataflow.getTransformationTime()).append(" ms").append(CCodeGenerator.NEWLINE);
        } else {
            sb.append("Internal error: null filter dataflow");
        }

        sb.append("*/");

        return sb.toString();
    }

    public void declareNodesReadMultipleTimes() throws DataflowException {
        // Determine read count for each node
        HashMap<Node, Integer> map = new HashMap<Node, Integer>();
        for (Node node : reachableNodeList) {
            if (node instanceof Operator) {
                for (Node child : ((Operator) node).getChildNodes()) {
                    Integer readCount = map.get(child);
                    if (readCount == null) {
                        readCount = 0;
                    } else {
                        readCount++;
                    }
                    map.put(child, readCount);
                }
            }
        }

        // If read count for some node is 2 or more, then declare the corresponding node
        for (Node node : map.keySet()) {
            Integer readCount = map.get(node);
            if (readCount > 1) {
                // StorageClass.EXTERNAL are not involved here
                node.setStorageClass(Node.StorageClass.INTERNAL_DECLARED);
            }
        }
    }

    private void undeclareMultiplyNodes() {
        for (Node node : reachableNodeList) {
            if (node instanceof Multiply) {
                node.setStorageClass(Node.StorageClass.INTERNAL_UNDECLARED);
            }
        }
    }

    private void undeclareOperators() {
        for (Node node : reachableNodeList) {
            if (node instanceof Operator) {
                node.setStorageClass(Node.StorageClass.INTERNAL_UNDECLARED);
            }
        }
    }

    public ArrayList<Operator> getParentListOf(Node node) {
        ArrayList<Operator> parentList = new ArrayList<Operator>();

        for (Node sample : reachableNodeList) {
            if (sample instanceof Operator) {
                Operator operator = (Operator) sample;
                if (operator.hasSuchChild(node)) {
                    parentList.add(operator);
                }
            }
        }

        return parentList;
    }

    private ArrayList<Multiply> collectMultiplyWith(long factor) {
        ArrayList<Multiply> result = new ArrayList<Multiply>();
        for (Node node : reachableNodeList) {
            if (node instanceof Multiply) {
                Multiply mul = (Multiply) node;
                for (int i = 0; i < mul.childArrayLength(); i++) {
                    Node child = mul.getChild(i);
                    if (child instanceof ConstIntegerLiteral) {
                        ConstIntegerLiteral literal = (ConstIntegerLiteral) child;
                        if (literal.getValue() == factor) {
                            result.add(mul);
                            break; // child iteration
                        }
                    }
                }
            }
        }
        return result;
    }

    /**
     * A type of optimization
     */
    public void shortcircuitMultiplyWith1() {
        buildReachableNodeList();

        ArrayList<Multiply> list = collectMultiplyWith(1);

        // Short-circuit collected multiply nodes
        if (!list.isEmpty()) {
            for (Multiply mul : list) {
                Node nonLiteral = null;
                for (int i = 0; i < mul.childArrayLength(); i++) {
                    Node node = mul.getChild(i);
                    if (!(node instanceof ConstIntegerLiteral)) {
                        nonLiteral = node;
                    }
                }
                if (nonLiteral == null) {
                    throw new RuntimeException("Invalid state in C-lang algorithm");
                }

                buildReachableNodeList();

                replaceChild(mul, nonLiteral);
            }
        }
    }

    /**
     * A type of optimization
     */
    public void removeMultiplyWith0() {
        buildReachableNodeList();

        ArrayList<Multiply> list = collectMultiplyWith(0);

        // Short-circuit collected multiply nodes
        if (!list.isEmpty()) {
            for (Multiply mul : list) {
                buildReachableNodeList();

                remove(mul);
            }
        }
    }

    public void replaceChild(Node destination, Node source) {
        ArrayList<Operator> parentList = getParentListOf(destination);
        for (Operator parent : parentList) {
            parent.replaceChild(destination, source);
        }
    }

    public void remove(Node node) {
        ArrayList<Operator> parentList = getParentListOf(node);
        for (Operator parent : parentList) {
            parent.removeChild(node, this);
        }
    }

    public void optimize() {
        removeMultiplyWith0();
        shortcircuitMultiplyWith1();
    }
}
